In vivo demonstration of the ultrasound-modulated light technique

We present, to our knowledge for the first time, results of ultrasound-modulated light signals on living tissues. In particular, we analyze, both theoretically and experimentally, the effect of speckle fluctuations on the signal. We find that two different kinds of noise compete--shot noise and speckle noise--and are present at different levels in static phantoms and ex vivo tissue samples on the one hand and in dynamic phantoms and living tissues on the other hand.     

Combinatorial Algorithms for the Unsplittable Flow Problem

We provide combinatorial algorithms for the unsplittable flow problem (UFP) that either match or improve the previously best results. In the UFP we are given a (possibly directed) capacitated graph with n vertices and m edges, and a set of terminal pairs each with its own demand and profit. The objective is to connect a subset of the terminal pairs each by a single flow path subject to the capacity constraints such that the total profit of the connected pairs is maximized.We consider three variants of the problem. First is the classical UFP in which the maximum demand is at most the minimum edge capacity. It was previously known to have an O(√m) approximation algorithm; the algorithm is based on the randomized rounding technique and its analysis makes use of the Chernoff bound and the FKG inequality.We provide a combinatorial algorithm that achieves the same approximation ratio and whose analysis is considerably simpler. Second is the extended UFP in which some demands might be higher than edge capacities. Our algorithm for this case improves the best known approximation ratio. We also give a lower bound that shows that the extended UFP is provably harder than the classical UFP. Finally, we consider the bounded UFP in which the maximum demand is at most 1/K times the minimum edge capacity for some K > 1. Here we provide combinatorial algorithms that match the currently best known algorithms. All of our algorithms are strongly polynomial and some can even be used in the online setting.     

Representation before computation

My main objective is to point out a fundamental weakness in the conventional conception of computation and suggest a promising way out. This weakness is directly related to a gross underestimation of the role of object representation in a computational model, hence confining such models to an unrealistic (input) environment, which, in turn, leads to “unnatural” computational models. This lack of appreciation of the role of structural object representation has been inherited from logic and partly from mathematics, where, in the latter, the centuries-old tradition is to represent objects as unstructured “points”. I also discuss why the appropriate fundamental reorientation in the conception of computational models will bring the resulting study of computation closer to the “natural” computational constrains. An example of the pertinent, class-oriented, representational formalism developed by our group over many years—Evolving Transformation System (ETS)—is briefly outlined here, and several related general lines of research are suggested.     

Lattice Distortions and Charge Carriers in Cuprates

A phenomenological model with itinerant bands and local states trapped by thelattice on the Cu-sites, is discussed to describe global features ofcuprates. Relative energy positions of localized and itinerant states beingtuned (thermodynamically or by doping), the system must undergo first-orderMott metal-insulator transition. Decreasing the local level (from themetallic end of a stoichiometric compound), charge separation instabilityoccurs first before the Mott transition. Crossing and hybridization betweenlocal (flat) and itinerant bands introduce a structure in density of stateswhich may account for pseudogap features in cuprates. Modelresults in polaronic lattice effects and is rich enough to serve as aphenomenology of cuprates.     

Buffer Management for Colored Packets with Deadlines

We consider buffer management of unit packets with deadlines for a multi-port device with reconfiguration overhead. The goal is to maximize the throughput of the device, i.e., the number of packets delivered by their deadline. For a single port or with free reconfiguration, the problem reduces to the well-known packets scheduling problem, where the celebrated earliest-deadline-first (EDF) strategy is optimal 1-competitive. However, EDF is not 1-competitive when there is a reconfiguration overhead. We design an online algorithm that achieves a competitive ratio of 1−o(1) when the ratio between the minimum laxity of the packets and the number of ports tends to infinity. This is one of the rare cases where one can design an almost 1-competitive algorithm. One ingredient of our analysis, which may be interesting on its own right, is a perturbation theorem on EDF for the classical packets scheduling problem. Specifically, we show that a small perturbation in the release and deadline times cannot significantly degrade the optimal throughput. This implies that EDF is robust in the sense that its throughput is close to the optimum even when the deadlines are not precisely known.     

A Preemptive Algorithm for Maximizing Disjoint Paths on Trees

We consider the on-line version of the maximum vertex disjoint path problem when the underlying network is a tree. In this problem, a sequence of requests arrives in an on-line fashion, where every request is a path in the tree. The on-line algorithm may accept a request only if it does not share a vertex with a previously accepted request. The goal is to maximize the number of accepted requests. It is known that no on-line algorithm can have a competitive ratio better than Ω(log n) for this problem, even if the algorithm is randomized and the tree is simply a line. Obviously, it is desirable to beat the logarithmic lower bound. Adler and Azar (Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithm, pp. 1–10, 1999) showed that if preemption is allowed (namely, previously accepted requests may be discarded, but once a request is discarded it can no longer be accepted), then there is a randomized on-line algorithm that achieves constant competitive ratio on the line. In the current work we present a randomized on-line algorithm with preemption that has constant competitive ratio on any tree. Our results carry over to the related problem of maximizing the number of accepted paths subject to a capacity constraint on vertices (in the disjoint path problem this capacity is 1). Moreover, if the available capacity is at least 4, randomization is not needed and our on-line algorithm becomes deterministic.     

Imprecise Reliability of General Structures

This paper discusses the important aspects of the reliability of systems with an imprecise general model of the structure function. It is assumed that the information about reliability behavior of components is restricted by the mean levels of component performance. In this case the classical reliability theory cannot provide a way for analyzing the reliability of systems. The theory of imprecise probabilities may be a basis in developing a general reliability theory which allows us to solve such problems. The basic tool for computing new reliability measures is the natural extension which can be regarded as a linear optimization problem. However, the linear programming computations will become impracticable when the number of components in the system is large. Therefore, the main aim of this paper is to obtain explicit expressions for computing the system reliability measures. We analyze the reliability of general structures and typical systems. The numerical examples illustrate the usefulness of the presented approach to reliability analyzing.     

Randomized range-maxima in nearly-constant parallel time

Given an array ofn input numbers, therange-maxima problem is that of preprocessing the data so that queries of the type what is the maximum value in subarray [i..j] can be answered quickly using one processor. We present a randomized preprocessing algorithm that runs inO(log^* n) time with high probability, using an optimal number of processors on a CRCW PRAM; each query can be processed in constant time by one processor. We also present a randomized algorithm for a parallel comparison model. Using an optimal number of processors, the preprocessing algorithm runs inO( (n)) time with high probability; each query can be processed inO ( (n)) time by one processor. (As is standard, (n) is the inverse of Ackermann function.) A constant time query can be achieved by some slowdown in the performance of the preprocessing stage.     

Titania and titania-silver nanoparticle deposits made by Liquid Flame Spray and their functionality as photocatalyst for organic- and biofilm removal

Titania and titania-silver nanoparticle deposits were made by Liquid Flame Spray technique, in which the liquid precursor is injected into a high temperature flame, where it will evaporate and nucleate to nanosize particles. One-step and two-step methods were used for preparation of titania-silver deposits. The amount of silver added was 1 wt%. The deposits were collected in the flame zone on steel and glass surfaces and were analyzed by TEM, EDS, XPS and SAXS. The titania deposits consisted of porous nanosized titania agglomerates of primary particles (~10 nm). With silver addition, small spherical silver metal particles (~2 nm) were detected on the agglomerates. An increase in the photocatalytic activity was verified by stearic acid decomposition and biofilm removal using Deinococcus geothermalis as the model organism.     

Fluorescent dye labeled bacteriophages--a new tracer for the investigation of viral transport in porous media: 1. Introduction and characterization

A new method for the study of pathogen transport in porous media is presented. The method is based on conjugation of fluorescent dyes to target bacteriophages and application of the modified bacteriophages for tracer studies. We demonstrate that the relevant transport determining properties of Rhodamine and several fluorescein-labeled phages are practically identical to those of the native bacteriophages. The advantages of the proposed method relative to direct enumeration of bacteriophages by plaque forming unit method, turbidity, fluorescent microspheres, and other alternative tracers are discussed. Notable advantages include simple quantitation by optical methods, unbiased signals even when virus aggregates are formed, and the ability to decouple inactivation kinetics from transport phenomena. Additionally, the signal reflects the removal and transport of the studied microorganism and not a surrogate.